home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / tk2.3 / dist / tkTextBTree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-17  |  65.6 KB  |  2,371 lines
  1. /* 
  2.  * tkTextBTree.c --
  3.  *
  4.  *    This file contains code that manages the B-tree representation
  5.  *    of text for Tk's text widget.  The B-tree holds both the text
  6.  *    and tag information related to the text.
  7.  *
  8.  * Copyright 1992 Regents of the University of California
  9.  * Permission to use, copy, modify, and distribute this
  10.  * software and its documentation for any purpose and without
  11.  * fee is hereby granted, provided that this copyright
  12.  * notice appears in all copies.  The University of California
  13.  * makes no representations about the suitability of this
  14.  * software for any purpose.  It is provided "as is" without
  15.  * express or implied warranty.
  16.  */
  17.  
  18. #ifndef lint
  19. static char rcsid[] = "$Header: /user6/ouster/wish/RCS/tkTextBTree.c,v 1.16 92/08/17 09:13:58 ouster Exp $ SPRITE (Berkeley)";
  20. #endif /* not lint */
  21.  
  22. #include "tkInt.h"
  23. #include "tkConfig.h"
  24. #include "tkText.h"
  25.  
  26.  
  27. /*
  28.  * The data structure below keeps summary information about one tag as part
  29.  * of the tag information in a node.
  30.  */
  31.  
  32. typedef struct Summary {
  33.     TkTextTag *tagPtr;            /* Handle for tag. */
  34.     int toggleCount;            /* Number of transitions into or
  35.                      * out of this tag that occur in
  36.                      * the subtree rooted at this node. */
  37.     struct Summary *nextPtr;        /* Next in list of all tags for same
  38.                      * node, or NULL if at end of list. */
  39. } Summary;
  40.  
  41. /*
  42.  * The data structure below defines a node in the B-tree representing
  43.  * all of the lines in a text widget.
  44.  */
  45.  
  46. typedef struct Node {
  47.     struct Node *parentPtr;        /* Pointer to parent node, or NULL if
  48.                      * this is the root. */
  49.     struct Node *nextPtr;        /* Next in list of children of the
  50.                      * same parent node, or NULL for end
  51.                      * of list. */
  52.     Summary *summaryPtr;        /* First in malloc-ed list of info
  53.                      * about tags in this subtree (NULL if
  54.                      * no tag info in the subtree). */
  55.     int level;                /* Level of this node in the B-tree.
  56.                      * 0 refers to the bottom of the tree
  57.                      * (children are lines, not nodes). */
  58.     union {                /* First in linked list of children. */
  59.     struct Node *nodePtr;        /* Used if level > 0. */
  60.     TkTextLine *linePtr;        /* Used if level == 0. */
  61.     } children;
  62.     int numChildren;            /* Number of children of this node. */
  63.     int numLines;            /* Total number of lines (leaves) in
  64.                      * the subtree rooted here. */
  65. } Node;
  66.  
  67. /*
  68.  * Upper and lower bounds on how many children a node may have:
  69.  * rebalance when either of these limits is exceeded.  MAX_CHILDREN
  70.  * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
  71.  */
  72.  
  73. #define MAX_CHILDREN 12
  74. #define MIN_CHILDREN 6
  75.  
  76. /*
  77.  * The data structure below defines an entire B-tree.
  78.  */
  79.  
  80. typedef struct BTree {
  81.     Node *rootPtr;            /* Pointer to root of B-tree. */
  82. } BTree;
  83.  
  84. /*
  85.  * The structure below is used to pass information between
  86.  * TkBTreeGetTags and IncCount:
  87.  */
  88.  
  89. typedef struct TagInfo {
  90.     int numTags;            /* Number of tags for which there
  91.                      * is currently information in
  92.                      * tags and counts. */
  93.     int arraySize;            /* Number of entries allocated for
  94.                      * tags and counts. */
  95.     TkTextTag **tagPtrs;        /* Array of tags seen so far.
  96.                      * Malloc-ed. */
  97.     int *counts;            /* Toggle count (so far) for each
  98.                      * entry in tags.  Malloc-ed. */
  99. } TagInfo;
  100.  
  101. /*
  102.  * Macro to compute the space needed for a line that holds n non-null
  103.  * characters:
  104.  */
  105.  
  106. #define LINE_SIZE(n) ((unsigned) (sizeof(TkTextLine) - 3 + (n)))
  107.  
  108. /*
  109.  * Variable that indicates whether to enable consistency checks for
  110.  * debugging.
  111.  */
  112.  
  113. int tkBTreeDebug = 0;
  114.  
  115. /*
  116.  * Forward declarations for procedures defined in this file:
  117.  */
  118.  
  119. static void        AddToggleToLine _ANSI_ARGS_((TkTextLine *linePtr,
  120.                 int index, TkTextTag *tagPtr));
  121. static void        ChangeNodeToggleCount _ANSI_ARGS_((Node *nodePtr,
  122.                 TkTextTag *tagPtr, int delta));
  123. static void        CheckNodeConsistency _ANSI_ARGS_((Node *nodePtr));
  124. static void        DeleteSummaries _ANSI_ARGS_((Summary *tagPtr));
  125. static void        DestroyNode _ANSI_ARGS_((Node *nodePtr));
  126. static void        IncCount _ANSI_ARGS_((TkTextTag *tagPtr, int inc,
  127.                 TagInfo *tagInfoPtr));
  128. static void        Rebalance _ANSI_ARGS_((BTree *treePtr, Node *nodePtr));
  129. static void        RecomputeNodeCounts _ANSI_ARGS_((Node *nodePtr));
  130.  
  131. /*
  132.  *----------------------------------------------------------------------
  133.  *
  134.  * TkBTreeCreate --
  135.  *
  136.  *    This procedure is called to create a new text B-tree.
  137.  *
  138.  * Results:
  139.  *    The return value is a pointer to a new B-tree containing
  140.  *    one line with nothing but a newline character.
  141.  *
  142.  * Side effects:
  143.  *    Memory is allocated and initialized.
  144.  *
  145.  *----------------------------------------------------------------------
  146.  */
  147.  
  148. TkTextBTree
  149. TkBTreeCreate()
  150. {
  151.     register BTree *treePtr;
  152.     register Node *rootPtr;
  153.     register TkTextLine *linePtr;
  154.  
  155.     rootPtr = (Node *) ckalloc(sizeof(Node));
  156.     linePtr = (TkTextLine *) ckalloc(LINE_SIZE(1));
  157.     rootPtr->parentPtr = NULL;
  158.     rootPtr->nextPtr = NULL;
  159.     rootPtr->summaryPtr = NULL;
  160.     rootPtr->level = 0;
  161.     rootPtr->children.linePtr = linePtr;
  162.     rootPtr->numChildren = 1;
  163.     rootPtr->numLines = 1;
  164.  
  165.     linePtr->parentPtr = rootPtr;
  166.     linePtr->nextPtr = NULL;
  167.     linePtr->annotPtr = NULL;
  168.     linePtr->numBytes = 1;
  169.     linePtr->bytes[0] = '\n';
  170.     linePtr->bytes[1] = 0;
  171.  
  172.     treePtr = (BTree *) ckalloc(sizeof(BTree));
  173.     treePtr->rootPtr = rootPtr;
  174.  
  175.     return (TkTextBTree) treePtr;
  176. }
  177.  
  178. /*
  179.  *----------------------------------------------------------------------
  180.  *
  181.  * TkBTreeDestroy --
  182.  *
  183.  *    Delete a B-tree, recycling all of the storage it contains.
  184.  *
  185.  * Results:
  186.  *    The tree given by treePtr is deleted.  TreePtr should never
  187.  *    again be used.
  188.  *
  189.  * Side effects:
  190.  *    Memory is freed.
  191.  *
  192.  *----------------------------------------------------------------------
  193.  */
  194.  
  195. void
  196. TkBTreeDestroy(tree)
  197.     TkTextBTree tree;            /* Pointer to tree to delete. */ 
  198. {
  199.     BTree *treePtr = (BTree *) tree;
  200.  
  201.     DestroyNode(treePtr->rootPtr);
  202.     ckfree((char *) treePtr);
  203. }
  204.  
  205. /*
  206.  *----------------------------------------------------------------------
  207.  *
  208.  * DestroyNode --
  209.  *
  210.  *    This is a recursive utility procedure used during the deletion
  211.  *    of a B-tree.
  212.  *
  213.  * Results:
  214.  *    None.
  215.  *
  216.  * Side effects:
  217.  *    All the storage for nodePtr and its descendants is freed.
  218.  *
  219.  *----------------------------------------------------------------------
  220.  */
  221.  
  222. static void
  223. DestroyNode(nodePtr)
  224.     register Node *nodePtr;
  225. {
  226.     if (nodePtr->level == 0) {
  227.     register TkTextLine *curPtr, *nextLinePtr;
  228.     register TkAnnotation *annotPtr, *nextAnnotPtr;
  229.  
  230.     for (curPtr = nodePtr->children.linePtr; curPtr != NULL; ) {
  231.         nextLinePtr = curPtr->nextPtr;
  232.         for (annotPtr = curPtr->annotPtr; annotPtr != NULL; ) {
  233.         nextAnnotPtr = annotPtr->nextPtr;
  234.         if (annotPtr->type == TK_ANNOT_TOGGLE) {
  235.             ckfree((char *) annotPtr);
  236.         }
  237.         annotPtr = nextAnnotPtr;
  238.         }
  239.         ckfree((char *) curPtr);
  240.         curPtr = nextLinePtr;
  241.     }
  242.     } else {
  243.     register Node *curPtr, *nextPtr;
  244.  
  245.     for (curPtr = nodePtr->children.nodePtr; curPtr != NULL; ) {
  246.         nextPtr = curPtr->nextPtr;
  247.         DestroyNode(curPtr);
  248.         curPtr = nextPtr;
  249.     }
  250.     }
  251.     DeleteSummaries(nodePtr->summaryPtr);
  252.     ckfree((char *) nodePtr);
  253. }
  254.  
  255. /*
  256.  *----------------------------------------------------------------------
  257.  *
  258.  * DeleteSummaries --
  259.  *
  260.  *    Free up all of the memory in a list of tag summaries associated
  261.  *    with a node.
  262.  *
  263.  * Results:
  264.  *    None.
  265.  *
  266.  * Side effects:
  267.  *    Storage is released.
  268.  *
  269.  *----------------------------------------------------------------------
  270.  */
  271.  
  272. static void
  273. DeleteSummaries(summaryPtr)
  274.     register Summary *summaryPtr;    /* First in list of node's tag
  275.                      * summaries. */
  276. {
  277.     register Summary *nextPtr;
  278.     while (summaryPtr != NULL) {
  279.     nextPtr = summaryPtr->nextPtr;
  280.     ckfree((char *) summaryPtr);
  281.     summaryPtr = nextPtr;
  282.     }
  283. }
  284.  
  285. /*
  286.  *----------------------------------------------------------------------
  287.  *
  288.  * TkBTreeInsertChars --
  289.  *
  290.  *    Insert characters at a given position in a B-tree.
  291.  *
  292.  * Results:
  293.  *    None.
  294.  *
  295.  * Side effects:
  296.  *    NumBytes characters are added to the B-tree at the given
  297.  *    character position.  This can cause the structure of the
  298.  *    B-tree to change.
  299.  *
  300.  *----------------------------------------------------------------------
  301.  */
  302.  
  303. void
  304. TkBTreeInsertChars(tree, linePtr, ch, string)
  305.     TkTextBTree tree;            /* B-tree in which to insert. */
  306.     register TkTextLine *linePtr;    /* Pointer to line in which to
  307.                      * insert. */
  308.     int ch;                /* Index of character before which
  309.                      * to insert.  Must not be after
  310.                      * last character in line.*/
  311.     char *string;            /* Pointer to bytes to insert (may
  312.                      * contain newlines, must be null-
  313.                      * terminated). */
  314. {
  315.     BTree *treePtr = (BTree *) tree;
  316.     register Node *nodePtr;
  317.     register TkAnnotation *annotPtr;
  318.     TkTextLine *prevPtr;
  319.     int newChunkLength;            /* # chars in current line being
  320.                      * inserted. */
  321.     register char *eol;            /* Pointer to last character in
  322.                      * current line being inserted. */
  323.     int changeToLineCount;        /* Counts change to total number of
  324.                      * lines in file. */
  325.     TkAnnotation *afterPtr;        /* List of annotations that occur
  326.                      * at or after the insertion point
  327.                      * in the line of the insertion. */
  328.     int prefixLength, suffixLength, totalLength;
  329.     register TkTextLine *newPtr;
  330.  
  331.     /*
  332.      * Find the line just before the one where the insertion will occur
  333.      * but with the same parent node (if there is one).  This is needed
  334.      * so we can replace the insertion line with a new one.  Remove this
  335.      * line from the list for its parent, since it's going to be discarded
  336.      * when we're all done).
  337.      */
  338.  
  339.     nodePtr = linePtr->parentPtr;
  340.     prevPtr = nodePtr->children.linePtr;
  341.     if (prevPtr == linePtr) {
  342.     prevPtr = NULL;
  343.     nodePtr->children.linePtr = linePtr->nextPtr;
  344.     } else {
  345.     for ( ; prevPtr->nextPtr != linePtr;  prevPtr = prevPtr->nextPtr) {
  346.         /* Empty loop body. */
  347.     }
  348.     prevPtr->nextPtr = linePtr->nextPtr;
  349.     }
  350.  
  351.     /*
  352.      * Break up the annotations for the insertion line into two pieces:
  353.      * those before the insertion point, and those at or after the insertion
  354.      * point.
  355.      */
  356.  
  357.     afterPtr = NULL;
  358.     if ((linePtr->annotPtr != NULL) && (linePtr->annotPtr->ch >= ch)) {
  359.     afterPtr = linePtr->annotPtr;
  360.     linePtr->annotPtr = NULL;
  361.     } else {
  362.     for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
  363.         annotPtr = annotPtr->nextPtr) {
  364.         if ((annotPtr->nextPtr != NULL)
  365.             && (annotPtr->nextPtr->ch >= ch)) {
  366.         afterPtr = annotPtr->nextPtr;
  367.         annotPtr->nextPtr = NULL;
  368.         break;
  369.         }
  370.     }
  371.     }
  372.  
  373.     /*
  374.      * Chop the string up into lines and insert each line individually.
  375.      */
  376.  
  377.     changeToLineCount = -1;
  378.     prefixLength = ch;
  379.     while (1) {
  380.     for (newChunkLength = 0, eol = string; *eol != 0; eol++) {
  381.         newChunkLength++;
  382.         if (*eol == '\n') {
  383.         break;
  384.         }
  385.     }
  386.  
  387.     /*
  388.      * Create a new line consisting of up to three parts: a prefix
  389.      * from linePtr, some material from string, and a suffix from
  390.      * linePtr.
  391.      */
  392.  
  393.     if ((newChunkLength == 0) || (*eol != '\n')) {
  394.         suffixLength = linePtr->numBytes - ch;
  395.     } else {
  396.         suffixLength = 0;
  397.     }
  398.     totalLength = prefixLength + newChunkLength + suffixLength;
  399.     newPtr = (TkTextLine *) ckalloc(LINE_SIZE(totalLength));
  400.     newPtr->parentPtr = nodePtr;
  401.     if (prevPtr == NULL) {
  402.         newPtr->nextPtr = nodePtr->children.linePtr;
  403.         nodePtr->children.linePtr = newPtr;
  404.     } else {
  405.         newPtr->nextPtr = prevPtr->nextPtr;
  406.         prevPtr->nextPtr = newPtr;
  407.     }
  408.     if (linePtr->annotPtr != NULL) {
  409.         newPtr->annotPtr = linePtr->annotPtr;
  410.         for (annotPtr = newPtr->annotPtr; annotPtr != NULL;
  411.             annotPtr = annotPtr->nextPtr) {
  412.         annotPtr->linePtr = newPtr;
  413.         }
  414.         linePtr->annotPtr = NULL;
  415.     } else {
  416.         newPtr->annotPtr = NULL;
  417.     }
  418.     newPtr->numBytes = totalLength;
  419.     if (prefixLength != 0) {
  420.         memcpy((VOID *) newPtr->bytes, (VOID *) linePtr->bytes,
  421.             prefixLength);
  422.     }
  423.     if (newChunkLength != 0) {
  424.         memcpy((VOID *) (newPtr->bytes + prefixLength), (VOID *) string,
  425.             newChunkLength);
  426.     }
  427.     if (suffixLength != 0) {
  428.         memcpy((VOID *) (newPtr->bytes + prefixLength + newChunkLength),
  429.             (VOID *) (linePtr->bytes + ch), suffixLength);
  430.     }
  431.     newPtr->bytes[totalLength] = 0;
  432.     changeToLineCount += 1;
  433.  
  434.     /*
  435.      * Quit after the suffix has been output (there is always at least
  436.      * one character of suffix: the newline).  Before jumping out of the
  437.      * loop, put back the annotations that pertain to the suffix.
  438.      * Careful!  If no newlines were inserted, there could already be
  439.      * annotations at the beginning of the line;  add back to the end.
  440.      */
  441.  
  442.     if (suffixLength != 0) {
  443.         if (newPtr->annotPtr == NULL) {
  444.         newPtr->annotPtr = afterPtr;
  445.         } else {
  446.         for (annotPtr = newPtr->annotPtr; annotPtr->nextPtr != NULL;
  447.             annotPtr = annotPtr->nextPtr) {
  448.             /* Empty loop body. */
  449.         }
  450.         annotPtr->nextPtr = afterPtr;
  451.         }
  452.         for (annotPtr = afterPtr; annotPtr != NULL;
  453.             annotPtr = annotPtr->nextPtr) {
  454.         annotPtr->linePtr = newPtr;
  455.         annotPtr->ch += prefixLength+newChunkLength-ch;
  456.         }
  457.         break;
  458.     }
  459.  
  460.     /*
  461.      * Advance to insert the next line chunk.
  462.      */
  463.  
  464.     string += newChunkLength;
  465.     prefixLength = 0;
  466.     prevPtr = newPtr;
  467.     }
  468.  
  469.     /*
  470.      * Increment the line counts in all the parent nodes of the insertion
  471.      * point, then rebalance the tree if necessary.
  472.      */
  473.  
  474.     for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
  475.     nodePtr->numLines += changeToLineCount;
  476.     }
  477.     nodePtr = linePtr->parentPtr;
  478.     nodePtr->numChildren += changeToLineCount;
  479.     if (nodePtr->numChildren > MAX_CHILDREN) {
  480.     Rebalance(treePtr, nodePtr);
  481.     }
  482.  
  483.     ckfree((char *) linePtr);
  484.     if (tkBTreeDebug) {
  485.     TkBTreeCheck(tree);
  486.     }
  487. }
  488.  
  489. /*
  490.  *----------------------------------------------------------------------
  491.  *
  492.  * TkBTreeDeleteChars --
  493.  *
  494.  *    Delete a range of characters from a B-tree.
  495.  *
  496.  * Results:
  497.  *    None.
  498.  *
  499.  * Side effects:
  500.  *    Information is deleted from the B-tree.  This can cause the
  501.  *    internal structure of the B-tree to change.  Note: the two
  502.  *    lines given by line1Ptr and line2Ptr will be replaced with
  503.  *    a single line containing the undeleted parts of the original
  504.  *    lines.  This could potentially result in an empty line;
  505.  *    normally the caller should adjust the deletion range to prevent
  506.  *    this sort of behavior.
  507.  *
  508.  *----------------------------------------------------------------------
  509.  */
  510.  
  511. void
  512. TkBTreeDeleteChars(tree, line1Ptr, ch1, line2Ptr, ch2)
  513.     TkTextBTree tree;            /* B-tree in which to delete. */
  514.     register TkTextLine *line1Ptr;    /* Line containing first character
  515.                      * to delete. */
  516.     int ch1;                /* Index within linePtr1 of first
  517.                      * character to delete. */
  518.     register TkTextLine *line2Ptr;    /* Line containing character just
  519.                      * after last one to delete. */
  520.     int ch2;                /* Index within linePtr2 of character
  521.                      * just after last one to delete. */
  522. {
  523.     BTree *treePtr = (BTree *) tree;
  524.     TkTextLine *linePtr, *nextPtr, *prevLinePtr;
  525.     Node *nodePtr, *parentPtr, *nextNodePtr;
  526.     TkAnnotation *annotPtr, *annotPtr2;
  527.     int ch;
  528.     int linesDeleted;            /* Counts lines deleted from current
  529.                      * level-0 node. */
  530.  
  531.     /*
  532.      * Work through the tree deleting all of the lines between line1Ptr
  533.      * and line2Ptr (but don't delete line1Ptr or line2Ptr yet).  Also
  534.      * delete any nodes in the B-tree that become empty because of
  535.      * this process.
  536.      */
  537.  
  538.     linePtr = line1Ptr->nextPtr;
  539.     nodePtr = line1Ptr->parentPtr;
  540.     if (line1Ptr == line2Ptr) {
  541.     goto middleLinesDeleted;
  542.     }
  543.     while (1) {
  544.  
  545.     /*
  546.      * Delete all relevant lines within the same level-0 node.
  547.      */
  548.  
  549.     linesDeleted = 0;
  550.     while ((linePtr != line2Ptr) && (linePtr != NULL)) {
  551.         /*
  552.          * Move any annotations in this line to the end of the
  553.          * deletion range.  If both the starting and ending toggle
  554.          * for a tagged range get moved, they'll cancel each other
  555.          * automatically and be dropped, which is the right behavior.
  556.          */
  557.  
  558.         for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
  559.             annotPtr = annotPtr2) {
  560.         if (annotPtr->type == TK_ANNOT_TOGGLE) {
  561.             AddToggleToLine(line2Ptr, ch2, annotPtr->info.tagPtr);
  562.             ChangeNodeToggleCount(nodePtr, annotPtr->info.tagPtr, -1);
  563.             annotPtr2 = annotPtr->nextPtr;
  564.             ckfree((char *) annotPtr);
  565.         } else {
  566.             annotPtr2 = annotPtr->nextPtr;
  567.             TkBTreeRemoveAnnotation(annotPtr);
  568.             annotPtr->linePtr = line2Ptr;
  569.             annotPtr->ch = ch2;
  570.             TkBTreeAddAnnotation(annotPtr);
  571.         }
  572.         }
  573.         nextPtr = linePtr->nextPtr;
  574.         ckfree((char *) linePtr);
  575.         linesDeleted++;
  576.         linePtr = nextPtr;
  577.     }
  578.     if (nodePtr == line1Ptr->parentPtr) {
  579.         line1Ptr->nextPtr = linePtr;
  580.     } else {
  581.         nodePtr->children.linePtr = linePtr;
  582.     }
  583.     for (parentPtr = nodePtr; parentPtr != NULL;
  584.         parentPtr = parentPtr->parentPtr) {
  585.         parentPtr->numLines -= linesDeleted;
  586.     }
  587.     nodePtr->numChildren -= linesDeleted;
  588.     if (linePtr == line2Ptr) {
  589.         break;
  590.     }
  591.  
  592.     /*
  593.      * Find the next level-0 node to visit, and its first line (but
  594.      * remember the current node so we can come back to delete it if
  595.      * it's empty).
  596.      */
  597.  
  598.     nextNodePtr = nodePtr;
  599.     while (nextNodePtr->nextPtr == NULL) {
  600.         nextNodePtr = nextNodePtr->parentPtr;
  601.     }
  602.     nextNodePtr = nextNodePtr->nextPtr;
  603.     while (nextNodePtr->level > 0) {
  604.         nextNodePtr = nextNodePtr->children.nodePtr;
  605.     }
  606.     linePtr = nextNodePtr->children.linePtr;
  607.  
  608.     /*
  609.      * Now go back to the node we just left and delete it if
  610.      * it's empty, along with any of its ancestors that are
  611.      * empty.  It may seem funny to go back like this, but it's
  612.      * simpler to find the next place to visit before modifying
  613.      * the tree structure.
  614.      */
  615.  
  616.     while (nodePtr->numChildren == 0) {
  617.         parentPtr = nodePtr->parentPtr;
  618.         if (parentPtr->children.nodePtr == nodePtr) {
  619.         parentPtr->children.nodePtr = nodePtr->nextPtr;
  620.         } else {
  621.         Node *prevPtr;
  622.  
  623.         for (prevPtr = parentPtr->children.nodePtr;
  624.             prevPtr->nextPtr != nodePtr;
  625.             prevPtr = prevPtr->nextPtr) {
  626.         }
  627.         prevPtr->nextPtr = nodePtr->nextPtr;
  628.         }
  629.         parentPtr->numChildren--;
  630.         DeleteSummaries(nodePtr->summaryPtr);
  631.         ckfree((char *) nodePtr);
  632.         nodePtr = parentPtr;
  633.     }
  634.     nodePtr = nextNodePtr;
  635.     }
  636.  
  637.     /*
  638.      * Make a new line that consists of the first part of the first
  639.      * line of the deletion range and the last part of the last line
  640.      * of the deletion range.
  641.      */
  642.  
  643.     middleLinesDeleted:
  644.     nodePtr = line1Ptr->parentPtr;
  645.     linePtr = (TkTextLine *) ckalloc(LINE_SIZE(ch1 + line2Ptr->numBytes - ch2));
  646.     linePtr->parentPtr = nodePtr;
  647.     linePtr->nextPtr = line1Ptr->nextPtr;
  648.     linePtr->annotPtr = NULL;
  649.     linePtr->numBytes = ch1 + line2Ptr->numBytes - ch2;
  650.     if (ch1 != 0) {
  651.     memcpy((VOID *) linePtr->bytes, (VOID *) line1Ptr->bytes, ch1);
  652.     }
  653.     strcpy(linePtr->bytes + ch1, line2Ptr->bytes + ch2);
  654.  
  655.     /*
  656.      * Process the annotations for the starting and ending lines.  Enter
  657.      * a new annotation on linePtr (the joined line) for each of these
  658.      * annotations, then delete the originals.  The code below is a little
  659.      * tricky (e.g. the "break" in the first loop) to handle the case where
  660.      * the starting and ending lines are the same.
  661.      */
  662.  
  663.     for (annotPtr = line1Ptr->annotPtr; annotPtr != NULL;
  664.         annotPtr = line1Ptr->annotPtr) {
  665.     if (annotPtr->ch <= ch1) {
  666.         ch = annotPtr->ch;
  667.     } else {
  668.         if (line1Ptr == line2Ptr) {
  669.         break;
  670.         }
  671.         ch = ch1;
  672.     }
  673.     line1Ptr->annotPtr = annotPtr->nextPtr;
  674.     if (annotPtr->type == TK_ANNOT_TOGGLE) {
  675.         AddToggleToLine(linePtr, ch, annotPtr->info.tagPtr);
  676.         ChangeNodeToggleCount(line1Ptr->parentPtr, annotPtr->info.tagPtr,
  677.             -1);
  678.         ckfree((char *) annotPtr);
  679.     } else {
  680.         annotPtr->linePtr = linePtr;
  681.         annotPtr->ch = ch;
  682.         TkBTreeAddAnnotation(annotPtr);
  683.     }
  684.     }
  685.     for (annotPtr = line2Ptr->annotPtr; annotPtr != NULL;
  686.         annotPtr = line2Ptr->annotPtr) {
  687.     if (annotPtr->ch >= ch2) {
  688.         ch = annotPtr->ch - ch2 + ch1;
  689.     } else {
  690.         ch = ch1;
  691.     }
  692.     line2Ptr->annotPtr = annotPtr->nextPtr;
  693.     if (annotPtr->type == TK_ANNOT_TOGGLE) {
  694.         AddToggleToLine(linePtr, ch, annotPtr->info.tagPtr);
  695.         ChangeNodeToggleCount(line2Ptr->parentPtr, annotPtr->info.tagPtr,
  696.             -1);
  697.         ckfree((char *) annotPtr);
  698.     } else {
  699.         annotPtr->linePtr = linePtr;
  700.         annotPtr->ch = ch;
  701.         TkBTreeAddAnnotation(annotPtr);
  702.     }
  703.     }
  704.  
  705.     /*
  706.      * Delete the original starting and stopping lines (don't forget
  707.      * that the annotations have already been deleted) and insert the
  708.      * new line in place of line1Ptr.
  709.      */
  710.  
  711.     nodePtr = line1Ptr->parentPtr;
  712.     if (nodePtr->children.linePtr == line1Ptr) {
  713.     nodePtr->children.linePtr = linePtr;
  714.     } else {
  715.     for (prevLinePtr = nodePtr->children.linePtr;
  716.         prevLinePtr->nextPtr != line1Ptr;
  717.         prevLinePtr = prevLinePtr->nextPtr) {
  718.         /* Empty loop body. */
  719.     }
  720.     prevLinePtr->nextPtr = linePtr;
  721.     }
  722.     ckfree((char *) line1Ptr);
  723.     nodePtr = line2Ptr->parentPtr;
  724.     if (line2Ptr != line1Ptr) {
  725.     if (nodePtr->children.linePtr == line2Ptr) {
  726.         nodePtr->children.linePtr = line2Ptr->nextPtr;
  727.     } else {
  728.         for (prevLinePtr = nodePtr->children.linePtr;
  729.             prevLinePtr->nextPtr != line2Ptr;
  730.             prevLinePtr = prevLinePtr->nextPtr) {
  731.         /* Empty loop body. */
  732.         }
  733.         prevLinePtr->nextPtr = line2Ptr->nextPtr;
  734.     }
  735.     ckfree((char *) line2Ptr);
  736.     for (parentPtr = nodePtr; parentPtr != NULL;
  737.         parentPtr = parentPtr->parentPtr) {
  738.         parentPtr->numLines--;
  739.     }
  740.     nodePtr->numChildren--;
  741.     }
  742.  
  743.     /*
  744.      * Rebalance the tree, starting from each of the endpoints of the
  745.      * deletion range.  This code is a tricky, because the act of
  746.      * rebalancing the parent of one endpoint can cause the parent of
  747.      * the other endpoint to be reallocated.  The only thing it's safe
  748.      * to hold onto is a pointer to a line.  Thus, rebalance line2Ptr's
  749.      * parent first, then use linePtr find the second parent to rebalance
  750.      * second.  
  751.      */
  752.  
  753.     if (nodePtr != linePtr->parentPtr) {
  754.     Rebalance(treePtr, nodePtr);
  755.     }
  756.     Rebalance(treePtr, linePtr->parentPtr);
  757.     if (tkBTreeDebug) {
  758.     TkBTreeCheck(tree);
  759.     }
  760. }
  761.  
  762. /*
  763.  *----------------------------------------------------------------------
  764.  *
  765.  * TkBTreeTag --
  766.  *
  767.  *    Turn a given tag on or off for a given range of characters in
  768.  *    a B-tree of text.
  769.  *
  770.  * Results:
  771.  *    None.
  772.  *
  773.  * Side effects:
  774.  *    The given tag is added to the given range of characters
  775.  *    in the tree or removed from all those characters, depending
  776.  *    on the "add" argument.
  777.  *
  778.  *----------------------------------------------------------------------
  779.  */
  780.  
  781. void
  782. TkBTreeTag(tree, line1, ch1, line2, ch2, tagPtr, add)
  783.     TkTextBTree tree;            /* B-tree in which to add tag
  784.                      * information. */
  785.     int line1, ch1;            /* Position of first character to
  786.                      * tag. */
  787.     int line2, ch2;            /* Position of character just after
  788.                      * last one to tag. */
  789.     TkTextTag *tagPtr;            /* Tag to associate with the range
  790.                      * of characters. */
  791.     int add;                /* One means add tag to the given
  792.                      * range of characters;  zero means
  793.                      * remove the tag from the range. */
  794. {
  795.     BTree *treePtr = (BTree *) tree;
  796.     register TkTextLine *line1Ptr, *line2Ptr;
  797.     TkTextSearch search;
  798.     int oldState;
  799.  
  800.     /*
  801.      * Find the lines containing the first and last characters to be tagged,
  802.      * and adjust the starting and stopping locations if they don't already
  803.      * point within lines.  If the range would have started or stopped at the
  804.      * end of a line, round it up to the beginning of the next line (right
  805.      * now this restriction keeps the final newline from being tagged).
  806.      */
  807.  
  808.     if (line1 < 0) {
  809.     line1 = 0;
  810.     ch1 = 0;
  811.     }
  812.     line1Ptr = TkBTreeFindLine(tree, line1);
  813.     if (line1Ptr == NULL) {
  814.     return;
  815.     }
  816.     if (ch1 >= line1Ptr->numBytes) {
  817.     TkTextLine *nextLinePtr;
  818.  
  819.     nextLinePtr = TkBTreeNextLine(line1Ptr);
  820.     if (nextLinePtr == NULL) {
  821.         return;
  822.     } else {
  823.         line1Ptr = nextLinePtr;
  824.         line1++;
  825.         ch1 = 0;
  826.     }
  827.     }
  828.     if (line2 < 0) {
  829.     return;
  830.     }
  831.     line2Ptr = TkBTreeFindLine(tree, line2);
  832.     if (line2Ptr == NULL) {
  833.     line2Ptr = TkBTreeFindLine(tree, treePtr->rootPtr->numLines-1);
  834.     ch2 = line2Ptr->numBytes-1;
  835.     }
  836.     if (ch2 >= line2Ptr->numBytes) {
  837.     TkTextLine *nextLinePtr;
  838.  
  839.     nextLinePtr = TkBTreeNextLine(line2Ptr);
  840.     if (nextLinePtr == NULL) {
  841.         ch2 = line2Ptr->numBytes-1;
  842.     } else {
  843.         line2Ptr = nextLinePtr;
  844.         line2++;
  845.         ch2 = 0;
  846.     }
  847.     }
  848.  
  849.     /*
  850.      * See if the tag is already present or absent at the start of the
  851.      * range.  If the state doesn't already match what we want then add
  852.      * a toggle there.
  853.      */
  854.  
  855.     oldState = TkBTreeCharTagged(line1Ptr, ch1, tagPtr);
  856.     if ((add != 0) ^ oldState) {
  857.     AddToggleToLine(line1Ptr, ch1, tagPtr);
  858.     }
  859.  
  860.     /*
  861.      * Scan the range of characters covered by the change and delete
  862.      * any existing tag transitions except those on the first and
  863.      * last characters.  Keep track of whether the old state just before
  864.      * the last character (not including any tags on it) is what we
  865.      * want now;  if not, then add a tag toggle there.
  866.      */
  867.  
  868.     TkBTreeStartSearch(tree, line1, ch1+1, line2, ch2, tagPtr, &search);
  869.     while (TkBTreeNextTag(&search)) {
  870.     if ((search.linePtr == line2Ptr) && (search.ch1 == ch2)) {
  871.         break;
  872.     }
  873.     oldState ^= 1;
  874.     AddToggleToLine(search.linePtr, search.ch1, tagPtr);
  875.     }
  876.     if ((add != 0) ^ oldState) {
  877.     AddToggleToLine(line2Ptr, ch2, tagPtr);
  878.     }
  879.  
  880.     if (tkBTreeDebug) {
  881.     TkBTreeCheck(tree);
  882.     }
  883. }
  884.  
  885. /*
  886.  *----------------------------------------------------------------------
  887.  *
  888.  * TkBTreeAddAnnotation --
  889.  *
  890.  *    Given a filled in annotation, this procedure links it into
  891.  *    a B-tree structure so that it will track changes to the B-tree.
  892.  *
  893.  * Results:
  894.  *    None.
  895.  *
  896.  * Side effects:
  897.  *    AnnotPtr will be linked into its tree.  Note:  the storage for
  898.  *    annotPtr is assumed to have been malloc'ed by the caller.
  899.  *
  900.  *----------------------------------------------------------------------
  901.  */
  902.  
  903.     /* ARGSUSED */
  904. void
  905. TkBTreeAddAnnotation(annotPtr)
  906.     TkAnnotation *annotPtr;    /* Pointer to annotation.  The caller must
  907.                  * have filled in all the fields except the
  908.                  * "nextPtr" field.  The type should NOT be
  909.                  * TK_ANNOT_TOGGLE;  these annotations are
  910.                  * managed by the TkBTreeTag procedure. */
  911. {
  912.     register TkAnnotation *annotPtr2, *prevPtr;
  913.  
  914.     for (prevPtr = NULL, annotPtr2 = annotPtr->linePtr->annotPtr;
  915.         annotPtr2 != NULL;
  916.         prevPtr = annotPtr2, annotPtr2 = annotPtr2->nextPtr) {
  917.     if (annotPtr2->ch > annotPtr->ch) {
  918.         break;
  919.     }
  920.     }
  921.     if (prevPtr == NULL) {
  922.     annotPtr->nextPtr = annotPtr->linePtr->annotPtr;
  923.     annotPtr->linePtr->annotPtr = annotPtr;
  924.     } else {
  925.     annotPtr->nextPtr = prevPtr->nextPtr;
  926.     prevPtr->nextPtr = annotPtr;
  927.     }
  928. }
  929.  
  930. /*
  931.  *----------------------------------------------------------------------
  932.  *
  933.  * TkBTreeRemoveAnnotation --
  934.  *
  935.  *    This procedure unlinks an annotation from a B-tree so that
  936.  *    the annotation will no longer be managed by the B-tree code.
  937.  *
  938.  * Results:
  939.  *    None.
  940.  *
  941.  * Side effects:
  942.  *    AnnotPtr will be unlinked from its tree.  Note:  it is up to the
  943.  *    caller to free the storage for annotPtr, if that is desired.
  944.  *
  945.  *----------------------------------------------------------------------
  946.  */
  947.  
  948.     /* ARGSUSED */
  949. void
  950. TkBTreeRemoveAnnotation(annotPtr)
  951.     TkAnnotation *annotPtr;    /* Pointer to annotation, which must
  952.                  * have been linked into tree by a previous
  953.                  * call to TkBTreeAddAnnotation. */
  954. {
  955.     register TkAnnotation *prevPtr;
  956.  
  957.     if (annotPtr->linePtr->annotPtr == annotPtr) {
  958.     annotPtr->linePtr->annotPtr = annotPtr->nextPtr;
  959.     } else {
  960.     for (prevPtr = annotPtr->linePtr->annotPtr;
  961.         prevPtr->nextPtr != annotPtr;
  962.         prevPtr = prevPtr->nextPtr) {
  963.         /* Empty loop body. */
  964.     }
  965.     prevPtr->nextPtr = annotPtr->nextPtr;
  966.     }
  967. }
  968.  
  969. /*
  970.  *----------------------------------------------------------------------
  971.  *
  972.  * TkBTreeFindLine --
  973.  *
  974.  *    Find a particular line in a B-tree based on its line number.
  975.  *
  976.  * Results:
  977.  *    The return value is a pointer to the line structure for the
  978.  *    line whose index is "line", or NULL if no such line exists.
  979.  *
  980.  * Side effects:
  981.  *    None.
  982.  *
  983.  *----------------------------------------------------------------------
  984.  */
  985.  
  986. TkTextLine *
  987. TkBTreeFindLine(tree, line)
  988.     TkTextBTree tree;            /* B-tree in which to find line. */
  989.     int line;                /* Index of desired line. */
  990. {
  991.     BTree *treePtr = (BTree *) tree;
  992.     register Node *nodePtr;
  993.     register TkTextLine *linePtr;
  994.     int linesLeft;
  995.  
  996.     nodePtr = treePtr->rootPtr;
  997.     linesLeft = line;
  998.     if ((line < 0) || (line >= nodePtr->numLines)) {
  999.     return NULL;
  1000.     }
  1001.  
  1002.     /*
  1003.      * Work down through levels of the tree until a node is found at
  1004.      * level 0.
  1005.      */
  1006.  
  1007.     while (nodePtr->level != 0) {
  1008.     for (nodePtr = nodePtr->children.nodePtr;
  1009.         nodePtr->numLines <= linesLeft;
  1010.         nodePtr = nodePtr->nextPtr) {
  1011.         if (nodePtr == NULL) {
  1012.         panic("TkBTreeFindLine ran out of nodes");
  1013.         }
  1014.         linesLeft -= nodePtr->numLines;
  1015.     }
  1016.     }
  1017.  
  1018.     /*
  1019.      * Work through the lines attached to the level-0 node.
  1020.      */
  1021.  
  1022.     for (linePtr = nodePtr->children.linePtr; linesLeft > 0;
  1023.         linePtr = linePtr->nextPtr) {
  1024.     if (linePtr == NULL) {
  1025.         panic("TkBTreeFindLine ran out of lines");
  1026.     }
  1027.     linesLeft -= 1;
  1028.     }
  1029.     return linePtr;
  1030. }
  1031.  
  1032. /*
  1033.  *----------------------------------------------------------------------
  1034.  *
  1035.  * TkBTreeNextLine --
  1036.  *
  1037.  *    Given an existing line in a B-tree, this procedure locates the
  1038.  *    next line in the B-tree.  This procedure is used for scanning
  1039.  *    through the B-tree.
  1040.  *
  1041.  * Results:
  1042.  *    The return value is a pointer to the line that immediately
  1043.  *    follows linePtr, or NULL if there is no such line.
  1044.  *
  1045.  * Side effects:
  1046.  *    None.
  1047.  *
  1048.  *----------------------------------------------------------------------
  1049.  */
  1050.  
  1051. TkTextLine *
  1052. TkBTreeNextLine(linePtr)
  1053.     register TkTextLine *linePtr;    /* Pointer to existing line in
  1054.                      * B-tree. */
  1055. {
  1056.     register Node *nodePtr;
  1057.  
  1058.     if (linePtr->nextPtr != NULL) {
  1059.     return linePtr->nextPtr;
  1060.     }
  1061.  
  1062.     /*
  1063.      * This was the last line associated with the particular parent node.
  1064.      * Search up the tree for the next node, then search down from that
  1065.      * node to find the first line,
  1066.      */
  1067.  
  1068.     for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
  1069.     if (nodePtr->nextPtr != NULL) {
  1070.         nodePtr = nodePtr->nextPtr;
  1071.         break;
  1072.     }
  1073.     if (nodePtr->parentPtr == NULL) {
  1074.         return (TkTextLine *) NULL;
  1075.     }
  1076.     }
  1077.     while (nodePtr->level > 0) {
  1078.     nodePtr = nodePtr->children.nodePtr;
  1079.     }
  1080.     return nodePtr->children.linePtr;
  1081. }
  1082.  
  1083. /*
  1084.  *----------------------------------------------------------------------
  1085.  *
  1086.  * TkBTreeLineIndex --
  1087.  *
  1088.  *    Given a pointer to a line in a B-tree, return the numerical
  1089.  *    index of that line.
  1090.  *
  1091.  * Results:
  1092.  *    The result is the index of linePtr within the tree, where 0
  1093.  *    corresponds to the first line in the tree.
  1094.  *
  1095.  * Side effects:
  1096.  *    None.
  1097.  *
  1098.  *----------------------------------------------------------------------
  1099.  */
  1100.  
  1101. int
  1102. TkBTreeLineIndex(linePtr)
  1103.     TkTextLine *linePtr;        /* Pointer to existing line in
  1104.                      * B-tree. */
  1105. {
  1106.     register TkTextLine *linePtr2;
  1107.     register Node *nodePtr, *parentPtr, *nodePtr2;
  1108.     int index;
  1109.  
  1110.     /*
  1111.      * First count how many lines precede this one in its level-0
  1112.      * node.
  1113.      */
  1114.  
  1115.     nodePtr = linePtr->parentPtr;
  1116.     index = 0;
  1117.     for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr;
  1118.         linePtr2 = linePtr2->nextPtr) {
  1119.     if (linePtr2 == NULL) {
  1120.         panic("TkBTreeLineIndex couldn't find line");
  1121.     }
  1122.     index += 1;
  1123.     }
  1124.  
  1125.     /*
  1126.      * Now work up through the levels of the tree one at a time,
  1127.      * counting how many lines are in nodes preceding the current
  1128.      * node.
  1129.      */
  1130.  
  1131.     for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL;
  1132.         nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) {
  1133.     for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr;
  1134.         nodePtr2 = nodePtr2->nextPtr) {
  1135.         if (nodePtr2 == NULL) {
  1136.         panic("TkBTreeLineIndex couldn't find node");
  1137.         }
  1138.         index += nodePtr2->numLines;
  1139.     }
  1140.     }
  1141.     return index;
  1142. }
  1143.  
  1144. /*
  1145.  *----------------------------------------------------------------------
  1146.  *
  1147.  * TkBTreeStartSearch --
  1148.  *
  1149.  *    This procedure sets up a search for tag transitions involving
  1150.  *    a given tag (or all tags) in a given range of the text.
  1151.  *
  1152.  * Results:
  1153.  *    None.
  1154.  *
  1155.  * Side effects:
  1156.  *    The information at *searchPtr is set up so that subsequent calls
  1157.  *    to TkBTreeNextTag will return information about the locations of
  1158.  *    tag transitions.  Note that TkBTreeNextTag must be called to get
  1159.  *    the first transition.
  1160.  *
  1161.  *----------------------------------------------------------------------
  1162.  */
  1163.  
  1164. void
  1165. TkBTreeStartSearch(tree, line1, ch1, line2, ch2, tagPtr, searchPtr)
  1166.     TkTextBTree tree;            /* Tree to search. */
  1167.     int line1, ch1;            /* Character position at which to                         * start search (tags at this position
  1168.                      * will be returned). */
  1169.     int line2, ch2;            /* Character position at which to                         * stop search (tags at this position
  1170.                      * will be returned). */
  1171.     TkTextTag *tagPtr;            /* Tag to search for.  NULL means
  1172.                      * search for any tag. */
  1173.     register TkTextSearch *searchPtr;    /* Where to store information about
  1174.                      * search's progress. */
  1175. {
  1176.     register TkAnnotation *annotPtr;
  1177.  
  1178.     searchPtr->tree = tree;
  1179.     if (line1 < 0) {
  1180.     searchPtr->line1 = 0;
  1181.     searchPtr->ch1 = 0;
  1182.     } else {
  1183.     searchPtr->line1 = line1;
  1184.     searchPtr->ch1 = ch1;
  1185.     }
  1186.     searchPtr->line2 = line2;
  1187.     searchPtr->ch2 = ch2;
  1188.     searchPtr->tagPtr = tagPtr;
  1189.     searchPtr->allTags = (tagPtr == NULL);
  1190.  
  1191.     searchPtr->linePtr = TkBTreeFindLine(searchPtr->tree, searchPtr->line1);
  1192.     if (searchPtr->linePtr == NULL) {
  1193.     searchPtr->line1 = searchPtr->line2;
  1194.     searchPtr->ch1 = searchPtr->ch2;
  1195.     searchPtr->annotPtr = NULL;
  1196.     } else {
  1197.     for (annotPtr = searchPtr->linePtr->annotPtr;
  1198.         (annotPtr != NULL) && (annotPtr->ch < ch1);
  1199.         annotPtr = annotPtr->nextPtr) {
  1200.         /* Empty loop body. */
  1201.     }
  1202.     searchPtr->annotPtr = annotPtr;
  1203.     }
  1204. }
  1205.  
  1206. /*
  1207.  *----------------------------------------------------------------------
  1208.  *
  1209.  * TkBTreeNextTag --
  1210.  *
  1211.  *    Once a tag search has begun, successive calls to this procedure
  1212.  *    return successive tag toggles.  Note:  it is NOT SAFE to call this
  1213.  *    procedure if characters have been inserted into or deleted from
  1214.  *    the B-tree since the call to TkBTreeStartSearch.
  1215.  *
  1216.  * Results:
  1217.  *    The return value is 1 if another toggle was found that met the
  1218.  *    criteria specified in the call to TkBTreeStartSearch.  0 is
  1219.  *    returned if no more matching tag transitions were found.
  1220.  *
  1221.  * Side effects:
  1222.  *    Information in *searchPtr is modified to update the state of the
  1223.  *    search and indicate where the next tag toggle is located.
  1224.  *
  1225.  *----------------------------------------------------------------------
  1226.  */
  1227.  
  1228. int
  1229. TkBTreeNextTag(searchPtr)
  1230.     register TkTextSearch *searchPtr;    /* Information about search in
  1231.                      * progress;  must have been set up by
  1232.                      * call to TkBTreeStartSearch. */
  1233. {
  1234.     register TkAnnotation *annotPtr;
  1235.     register Node *nodePtr;
  1236.     register Summary *summaryPtr;
  1237.  
  1238.     if (searchPtr->linePtr == NULL) {
  1239.     return 0;
  1240.     }
  1241.  
  1242.     /*
  1243.      * The outermost loop iterates over lines that may potentially contain
  1244.      * a relevant tag transition, starting from the current line and tag.
  1245.      */
  1246.  
  1247.     while (1) {
  1248.     /*
  1249.      * See if there are more tags on the current line that are relevant.
  1250.      */
  1251.     
  1252.     for (annotPtr = searchPtr->annotPtr; annotPtr != NULL;
  1253.         annotPtr = annotPtr->nextPtr) {
  1254.         if ((annotPtr->type == TK_ANNOT_TOGGLE)
  1255.             && (searchPtr->allTags
  1256.             || (annotPtr->info.tagPtr == searchPtr->tagPtr))) {
  1257.         if ((searchPtr->line1 == searchPtr->line2)
  1258.             && (annotPtr->ch > searchPtr->ch2)) {
  1259.             goto searchOver;
  1260.         }
  1261.         searchPtr->tagPtr = annotPtr->info.tagPtr;
  1262.         searchPtr->ch1 = annotPtr->ch;
  1263.         searchPtr->annotPtr = annotPtr->nextPtr;
  1264.         return 1;
  1265.         }
  1266.     }
  1267.     
  1268.     /*
  1269.      * See if there are more lines associated with the current parent
  1270.      * node.  If so, go back to the top of the loop to search the next
  1271.      * one of them.
  1272.      */
  1273.     
  1274.     if (searchPtr->line1 >= searchPtr->line2) {
  1275.         goto searchOver;
  1276.     }
  1277.     searchPtr->line1++;
  1278.     if (searchPtr->linePtr->nextPtr != NULL) {
  1279.         searchPtr->linePtr = searchPtr->linePtr->nextPtr;
  1280.         searchPtr->annotPtr = searchPtr->linePtr->annotPtr;
  1281.         continue;
  1282.     }
  1283.     
  1284.     /*
  1285.      * Search across and up through the B-tree's node hierarchy looking
  1286.      * for the next node that has a relevant tag transition somewhere in
  1287.      * its subtree.  Be sure to update the current line number as we
  1288.      * skip over large chunks of lines.
  1289.      */
  1290.     
  1291.     nodePtr = searchPtr->linePtr->parentPtr;
  1292.     while (1) {
  1293.         while (nodePtr->nextPtr == NULL) {
  1294.         if (nodePtr->parentPtr == NULL) {
  1295.             goto searchOver;
  1296.         }
  1297.         nodePtr = nodePtr->parentPtr;
  1298.         }
  1299.         nodePtr = nodePtr->nextPtr;
  1300.         for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
  1301.             summaryPtr = summaryPtr->nextPtr) {
  1302.         if ((searchPtr->allTags) ||
  1303.             (summaryPtr->tagPtr == searchPtr->tagPtr)) {
  1304.             goto gotNodeWithTag;
  1305.         }
  1306.         }
  1307.         searchPtr->line1 += nodePtr->numLines;
  1308.     }
  1309.     
  1310.     /*
  1311.      * At this point we've found a subtree that has a relevant tag
  1312.      * transition.  Now search down (and across) through that subtree
  1313.      * to find the first level-0 node that has a relevant tag transition.
  1314.      */
  1315.     
  1316.     gotNodeWithTag:
  1317.     while (nodePtr->level > 0) {
  1318.         for (nodePtr = nodePtr->children.nodePtr; ;
  1319.             nodePtr = nodePtr->nextPtr) {
  1320.         for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
  1321.             summaryPtr = summaryPtr->nextPtr) {
  1322.             if ((searchPtr->allTags)
  1323.                 || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
  1324.             goto nextChild;
  1325.             }
  1326.         }
  1327.         searchPtr->line1 += nodePtr->numLines;
  1328.         if (nodePtr->nextPtr == NULL) {
  1329.             panic("TkBTreeNextTag found incorrect tag summary info.");
  1330.         }
  1331.         }
  1332.         nextChild:
  1333.         continue;
  1334.     }
  1335.     
  1336.     /*
  1337.      * Now we're down to a level-0 node that contains a line that contains
  1338.      * a relevant tag transition.  Set up line information and go back to
  1339.      * the beginning of the loop to search through lines.
  1340.      */
  1341.  
  1342.     searchPtr->linePtr = nodePtr->children.linePtr;
  1343.     searchPtr->annotPtr = searchPtr->linePtr->annotPtr;
  1344.     if (searchPtr->line1 > searchPtr->line2) {
  1345.         goto searchOver;
  1346.     }
  1347.     continue;
  1348.     }
  1349.  
  1350.     searchOver:
  1351.     searchPtr->line1 = searchPtr->line2;
  1352.     searchPtr->ch1 = searchPtr->ch2;
  1353.     searchPtr->annotPtr = NULL;
  1354.     searchPtr->linePtr = NULL;
  1355.     return 0;
  1356. }
  1357.  
  1358. /*
  1359.  *----------------------------------------------------------------------
  1360.  *
  1361.  * TkBTreeCheck --
  1362.  *
  1363.  *    This procedure runs a set of consistency checks over a B-tree
  1364.  *    and panics if any inconsistencies are found.
  1365.  *
  1366.  * Results:
  1367.  *    None.
  1368.  *
  1369.  * Side effects:
  1370.  *    If a structural defect is found, the procedure panics with an
  1371.  *    error message.
  1372.  *
  1373.  *----------------------------------------------------------------------
  1374.  */
  1375.  
  1376. void
  1377. TkBTreeCheck(tree)
  1378.     TkTextBTree tree;        /* Tree to check. */
  1379. {
  1380.     BTree *treePtr = (BTree *) tree;
  1381.     register Summary *summaryPtr;
  1382.  
  1383.     /*
  1384.      * Make sure that overall there is an even count of tag transitions
  1385.      * for the whole text.
  1386.      */
  1387.  
  1388.     for (summaryPtr = treePtr->rootPtr->summaryPtr; summaryPtr != NULL;
  1389.         summaryPtr = summaryPtr->nextPtr) {
  1390.     if (summaryPtr->toggleCount & 1) {
  1391.         panic("TkBTreeCheck found odd toggle count for \"%s\" (%d)",
  1392.             summaryPtr->tagPtr->name, summaryPtr->toggleCount);
  1393.     }
  1394.     }
  1395.  
  1396.     /*
  1397.      * Call a recursive procedure to do all of the rest of the checks.
  1398.      */
  1399.  
  1400.     CheckNodeConsistency(treePtr->rootPtr);
  1401. }
  1402.  
  1403. /*
  1404.  *----------------------------------------------------------------------
  1405.  *
  1406.  * Rebalance --
  1407.  *
  1408.  *    This procedure is called when a node of a B-tree appears to be
  1409.  *    out of balance (too many children, or too few).  It rebalances
  1410.  *    that node and all of its ancestors in the tree.
  1411.  *
  1412.  * Results:
  1413.  *    None.
  1414.  *
  1415.  * Side effects:
  1416.  *    The internal structure of treePtr may change.
  1417.  *
  1418.  *----------------------------------------------------------------------
  1419.  */
  1420.  
  1421. static void
  1422. Rebalance(treePtr, nodePtr)
  1423.     BTree *treePtr;            /* Tree that is being rebalanced. */
  1424.     register Node *nodePtr;        /* Node that may be out of balance. */
  1425. {
  1426.     /*
  1427.      * Loop over the entire ancestral chain of the node, working up
  1428.      * through the tree one node at a time until the root node has
  1429.      * been processed.
  1430.      */
  1431.  
  1432.     for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
  1433.     register Node *newPtr, *childPtr;
  1434.     register TkTextLine *linePtr;
  1435.     int i;
  1436.  
  1437.     /*
  1438.      * Check to see if the node has too many children.  If it does,
  1439.      * then split off all but the first MIN_CHILDREN into a separate
  1440.      * node following the original one.  Then repeat until the
  1441.      * node has a decent size.
  1442.      */
  1443.  
  1444.     if (nodePtr->numChildren > MAX_CHILDREN) {
  1445.         while (1) {
  1446.         /*
  1447.          * If the node being split is the root node, then make a
  1448.          * new root node above it first.
  1449.          */
  1450.     
  1451.         if (nodePtr->parentPtr == NULL) {
  1452.             newPtr = (Node *) ckalloc(sizeof(Node));
  1453.             newPtr->parentPtr = NULL;
  1454.             newPtr->nextPtr = NULL;
  1455.             newPtr->summaryPtr = NULL;
  1456.             newPtr->level = nodePtr->level + 1;
  1457.             newPtr->children.nodePtr = nodePtr;
  1458.             newPtr->numChildren = 1;
  1459.             newPtr->numLines = nodePtr->numLines;
  1460.             RecomputeNodeCounts(newPtr);
  1461.             treePtr->rootPtr = newPtr;
  1462.         }
  1463.         newPtr = (Node *) ckalloc(sizeof(Node));
  1464.         newPtr->parentPtr = nodePtr->parentPtr;
  1465.         newPtr->nextPtr = nodePtr->nextPtr;
  1466.         nodePtr->nextPtr = newPtr;
  1467.         newPtr->summaryPtr = NULL;
  1468.         newPtr->level = nodePtr->level;
  1469.         newPtr->numChildren = nodePtr->numChildren - MIN_CHILDREN;
  1470.         if (nodePtr->level == 0) {
  1471.             for (i = MIN_CHILDREN-1,
  1472.                 linePtr = nodePtr->children.linePtr;
  1473.                 i > 0; i--, linePtr = linePtr->nextPtr) {
  1474.             /* Empty loop body. */
  1475.             }
  1476.             newPtr->children.linePtr = linePtr->nextPtr;
  1477.             linePtr->nextPtr = NULL;
  1478.         } else {
  1479.             for (i = MIN_CHILDREN-1,
  1480.                 childPtr = nodePtr->children.nodePtr;
  1481.                 i > 0; i--, childPtr = childPtr->nextPtr) {
  1482.             /* Empty loop body. */
  1483.             }
  1484.             newPtr->children.nodePtr = childPtr->nextPtr;
  1485.             childPtr->nextPtr = NULL;
  1486.         }
  1487.         RecomputeNodeCounts(nodePtr);
  1488.         nodePtr->parentPtr->numChildren++;
  1489.         nodePtr = newPtr;
  1490.         if (nodePtr->numChildren <= MAX_CHILDREN) {
  1491.             RecomputeNodeCounts(nodePtr);
  1492.             break;
  1493.         }
  1494.         }
  1495.     }
  1496.  
  1497.     while (nodePtr->numChildren < MIN_CHILDREN) {
  1498.         register Node *otherPtr;
  1499.         Node *halfwayNodePtr = NULL;    /* Initialization needed only */
  1500.         TkTextLine *halfwayLinePtr = NULL;    /* to prevent cc warnings. */
  1501.         int totalChildren, firstChildren, i;
  1502.  
  1503.         /*
  1504.          * Too few children for this node.  If this is the root,
  1505.          * it's OK for it to have less than MIN_CHILDREN children
  1506.          * as long as it's got at least two.  If it has only one
  1507.          * (and isn't at level 0), then chop the root node out of
  1508.          * the tree and use its child as the new root.
  1509.          */
  1510.  
  1511.         if (nodePtr->parentPtr == NULL) {
  1512.         if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) {
  1513.             treePtr->rootPtr = nodePtr->children.nodePtr;
  1514.             treePtr->rootPtr->parentPtr = NULL;
  1515.             DeleteSummaries(nodePtr->summaryPtr);
  1516.             ckfree((char *) nodePtr);
  1517.         }
  1518.         return;
  1519.         }
  1520.  
  1521.         /*
  1522.          * Not the root.  Make sure that there are siblings to
  1523.          * balance with.
  1524.          */
  1525.  
  1526.         if (nodePtr->parentPtr->numChildren < 2) {
  1527.         Rebalance(treePtr, nodePtr->parentPtr);
  1528.         continue;
  1529.         }
  1530.  
  1531.         /*
  1532.          * Find a sibling to borrow from, and arrange for nodePtr to
  1533.          * be the earlier of the pair.
  1534.          */
  1535.  
  1536.         if (nodePtr->nextPtr == NULL) {
  1537.         for (otherPtr = nodePtr->parentPtr->children.nodePtr;
  1538.             otherPtr->nextPtr != nodePtr;
  1539.             otherPtr = otherPtr->nextPtr) {
  1540.             /* Empty loop body. */
  1541.         }
  1542.         nodePtr = otherPtr;
  1543.         }
  1544.         otherPtr = nodePtr->nextPtr;
  1545.  
  1546.         /*
  1547.          * We're going to either merge the two siblings together
  1548.          * into one node or redivide the children among them to
  1549.          * balance their loads.  As preparation, join their two
  1550.          * child lists into a single list and remember the half-way
  1551.          * point in the list.
  1552.          */
  1553.  
  1554.         totalChildren = nodePtr->numChildren + otherPtr->numChildren;
  1555.         firstChildren = totalChildren/2;
  1556.         if (nodePtr->children.nodePtr == NULL) {
  1557.         nodePtr->children = otherPtr->children;
  1558.         } else if (nodePtr->level == 0) {
  1559.         register TkTextLine *linePtr;
  1560.  
  1561.         for (linePtr = nodePtr->children.linePtr, i = 1;
  1562.             linePtr->nextPtr != NULL;
  1563.             linePtr = linePtr->nextPtr, i++) {
  1564.             if (i == firstChildren) {
  1565.             halfwayLinePtr = linePtr;
  1566.             }
  1567.         }
  1568.         linePtr->nextPtr = otherPtr->children.linePtr;
  1569.         while (i <= firstChildren) {
  1570.             halfwayLinePtr = linePtr;
  1571.             linePtr = linePtr->nextPtr;
  1572.             i++;
  1573.         }
  1574.         } else {
  1575.         register Node *childPtr;
  1576.  
  1577.         for (childPtr = nodePtr->children.nodePtr, i = 1;
  1578.             childPtr->nextPtr != NULL;
  1579.             childPtr = childPtr->nextPtr, i++) {
  1580.             if (i <= firstChildren) {
  1581.             if (i == firstChildren) {
  1582.                 halfwayNodePtr = childPtr;
  1583.             }
  1584.             }
  1585.         }
  1586.         childPtr->nextPtr = otherPtr->children.nodePtr;
  1587.         while (i <= firstChildren) {
  1588.             halfwayNodePtr = childPtr;
  1589.             childPtr = childPtr->nextPtr;
  1590.             i++;
  1591.         }
  1592.         }
  1593.  
  1594.         /*
  1595.          * If the two siblings can simply be merged together, do it.
  1596.          */
  1597.  
  1598.         if (totalChildren < MAX_CHILDREN) {
  1599.         RecomputeNodeCounts(nodePtr);
  1600.         nodePtr->nextPtr = otherPtr->nextPtr;
  1601.         nodePtr->parentPtr->numChildren--;
  1602.         DeleteSummaries(otherPtr->summaryPtr);
  1603.         ckfree((char *) otherPtr);
  1604.         continue;
  1605.         }
  1606.  
  1607.         /*
  1608.          * The siblings can't be merged, so just divide their
  1609.          * children evenly between them.
  1610.          */
  1611.  
  1612.         if (nodePtr->level == 0) {
  1613.         otherPtr->children.linePtr = halfwayLinePtr->nextPtr;
  1614.         halfwayLinePtr->nextPtr = NULL;
  1615.         } else {
  1616.         otherPtr->children.nodePtr = halfwayNodePtr->nextPtr;
  1617.         halfwayNodePtr->nextPtr = NULL;
  1618.         }
  1619.         RecomputeNodeCounts(nodePtr);
  1620.         RecomputeNodeCounts(otherPtr);
  1621.     }
  1622.     }
  1623. }
  1624.  
  1625. /*
  1626.  *----------------------------------------------------------------------
  1627.  *
  1628.  * RecomputeNodeCounts --
  1629.  *
  1630.  *    This procedure is called to recompute all the counts in a node
  1631.  *    (tags, child information, etc.) by scaning the information in
  1632.  *    its descendants.  This procedure is called during rebalancing
  1633.  *    when a node's child structure has changed.
  1634.  *
  1635.  * Results:
  1636.  *    None.
  1637.  *
  1638.  * Side effects:
  1639.  *    The tag counts for nodePtr are modified to reflect its current
  1640.  *    child structure, as are its numChildren and numLines fields.
  1641.  *    Also, all of the children's parentPtr fields are made to point
  1642.  *    to nodePtr.
  1643.  *
  1644.  *----------------------------------------------------------------------
  1645.  */
  1646.  
  1647. static void
  1648. RecomputeNodeCounts(nodePtr)
  1649.     register Node *nodePtr;        /* Node whose tag summary information
  1650.                      * must be recomputed. */
  1651. {
  1652.     register Summary *summaryPtr, *summaryPtr2;
  1653.     register Node *childPtr;
  1654.     register TkTextLine *linePtr;
  1655.     register TkAnnotation *annotPtr;
  1656.  
  1657.     /*
  1658.      * Zero out all the existing counts for the node, but don't delete
  1659.      * the existing Summary records (most of them will probably be reused).
  1660.      */
  1661.  
  1662.     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
  1663.         summaryPtr = summaryPtr->nextPtr) {
  1664.     summaryPtr->toggleCount = 0;
  1665.     }
  1666.     nodePtr->numChildren = 0;
  1667.     nodePtr->numLines = 0;
  1668.  
  1669.     /*
  1670.      * Scan through the children, adding the childrens' tag counts into
  1671.      * the node's tag counts and adding new Summarys to the node if
  1672.      * necessary.
  1673.      */
  1674.  
  1675.     if (nodePtr->level == 0) {
  1676.     for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
  1677.         linePtr = linePtr->nextPtr) {
  1678.         nodePtr->numChildren++;
  1679.         nodePtr->numLines++;
  1680.         linePtr->parentPtr = nodePtr;
  1681.         for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
  1682.             annotPtr = annotPtr->nextPtr) {
  1683.         if (annotPtr->type != TK_ANNOT_TOGGLE) {
  1684.             continue;
  1685.         }
  1686.         for (summaryPtr = nodePtr->summaryPtr; ;
  1687.             summaryPtr = summaryPtr->nextPtr) {
  1688.             if (summaryPtr == NULL) {
  1689.             summaryPtr = (Summary *) ckalloc(sizeof(Summary));
  1690.             summaryPtr->tagPtr = annotPtr->info.tagPtr;
  1691.             summaryPtr->toggleCount = 1;
  1692.             summaryPtr->nextPtr = nodePtr->summaryPtr;
  1693.             nodePtr->summaryPtr = summaryPtr;
  1694.             break;
  1695.             }
  1696.             if (summaryPtr->tagPtr == annotPtr->info.tagPtr) {
  1697.             summaryPtr->toggleCount++;
  1698.             break;
  1699.             }
  1700.         }
  1701.         }
  1702.     }
  1703.     } else {
  1704.     for (childPtr = nodePtr->children.nodePtr; childPtr != NULL;
  1705.         childPtr = childPtr->nextPtr) {
  1706.         nodePtr->numChildren++;
  1707.         nodePtr->numLines += childPtr->numLines;
  1708.         childPtr->parentPtr = nodePtr;
  1709.         for (summaryPtr2 = childPtr->summaryPtr; summaryPtr2 != NULL;
  1710.             summaryPtr2 = summaryPtr2->nextPtr) {
  1711.         for (summaryPtr = nodePtr->summaryPtr; ;
  1712.             summaryPtr = summaryPtr->nextPtr) {
  1713.             if (summaryPtr == NULL) {
  1714.             summaryPtr = (Summary *) ckalloc(sizeof(Summary));
  1715.             summaryPtr->tagPtr = summaryPtr2->tagPtr;
  1716.             summaryPtr->toggleCount = summaryPtr2->toggleCount;
  1717.             summaryPtr->nextPtr = nodePtr->summaryPtr;
  1718.             nodePtr->summaryPtr = summaryPtr;
  1719.             break;
  1720.             }
  1721.             if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
  1722.             summaryPtr->toggleCount += summaryPtr2->toggleCount;
  1723.             break;
  1724.             }
  1725.         }
  1726.         }
  1727.     }
  1728.     }
  1729.  
  1730.     /*
  1731.      * Scan through the node's tag records again and delete any Summary
  1732.      * records that still have a zero count.
  1733.      */
  1734.  
  1735.     summaryPtr2 = NULL;
  1736.     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; ) {
  1737.     if (summaryPtr->toggleCount > 0) {
  1738.         summaryPtr2 = summaryPtr;
  1739.         summaryPtr = summaryPtr->nextPtr;
  1740.         continue;
  1741.     }
  1742.     if (summaryPtr2 != NULL) {
  1743.         summaryPtr2->nextPtr = summaryPtr->nextPtr;
  1744.         ckfree((char *) summaryPtr);
  1745.         summaryPtr = summaryPtr2->nextPtr;
  1746.     } else {
  1747.         nodePtr->summaryPtr = summaryPtr->nextPtr;
  1748.         ckfree((char *) summaryPtr);
  1749.         summaryPtr = nodePtr->summaryPtr;
  1750.     }
  1751.     }
  1752. }
  1753.  
  1754. /*
  1755.  *----------------------------------------------------------------------
  1756.  *
  1757.  * AddToggleToLine --
  1758.  *
  1759.  *    Insert a tag transition at a particular point in a particular
  1760.  *    line.
  1761.  *
  1762.  * Results:
  1763.  *    None.
  1764.  *
  1765.  * Side effects:
  1766.  *    LinePtr and all its ancestors in the B-tree stucture are modified
  1767.  *    to indicate the presence of a transition (either on or off) on
  1768.  *    tag at the given place in the given line.
  1769.  *
  1770.  *----------------------------------------------------------------------
  1771.  */
  1772.  
  1773. static void
  1774. AddToggleToLine(linePtr, index, tagPtr)
  1775.     TkTextLine *linePtr;        /* Line within which to add
  1776.                      * transition. */
  1777.     int index;                /* Character before which to
  1778.                      * add transition. */
  1779.     TkTextTag *tagPtr;            /* Information about tag. */
  1780. {
  1781.     register TkAnnotation *annotPtr, *prevPtr;
  1782.     int delta = 1;
  1783.  
  1784.     /*
  1785.      * Find the position where the toggle should be inserted into
  1786.      * the array (just after prevPtr), and see if there is already
  1787.      * a toggle at exactly the point where we're going to insert a
  1788.      * new toggle.  If so then the two toggles cancel;  just delete
  1789.      * the existing toggle.
  1790.      */
  1791.  
  1792.     for (prevPtr = NULL, annotPtr = linePtr->annotPtr; annotPtr != NULL;
  1793.         prevPtr = annotPtr, annotPtr = annotPtr->nextPtr) {
  1794.     if (annotPtr->ch > index) {
  1795.         break;
  1796.     }
  1797.     if ((annotPtr->type == TK_ANNOT_TOGGLE)
  1798.         && (annotPtr->ch == index)
  1799.         && (annotPtr->info.tagPtr == tagPtr)) {
  1800.         if (prevPtr == NULL) {
  1801.         linePtr->annotPtr = annotPtr->nextPtr;
  1802.         } else {
  1803.         prevPtr->nextPtr = annotPtr->nextPtr;
  1804.         }
  1805.         ckfree((char *) annotPtr);
  1806.         delta = -1;
  1807.         goto updateNodes;
  1808.     }
  1809.     }
  1810.  
  1811.     /*
  1812.      * Create a new toggle and insert it into the list.
  1813.      */
  1814.  
  1815.     annotPtr = (TkAnnotation *) ckalloc(sizeof(TkAnnotation));
  1816.     annotPtr->type = TK_ANNOT_TOGGLE;
  1817.     annotPtr->linePtr = linePtr;
  1818.     annotPtr->ch = index;
  1819.     annotPtr->info.tagPtr = tagPtr;
  1820.     if (prevPtr == NULL) {
  1821.     annotPtr->nextPtr = linePtr->annotPtr;
  1822.     linePtr->annotPtr = annotPtr;
  1823.     } else {
  1824.     annotPtr->nextPtr = prevPtr->nextPtr;
  1825.     prevPtr->nextPtr = annotPtr;
  1826.     }
  1827.  
  1828.     /*
  1829.      * Update all the nodes above this line to reflect the change in
  1830.      * toggle structure.
  1831.      */
  1832.  
  1833.     updateNodes:
  1834.     ChangeNodeToggleCount(linePtr->parentPtr, tagPtr, delta);
  1835. }
  1836.  
  1837. /*
  1838.  *----------------------------------------------------------------------
  1839.  *
  1840.  * ChangeNodeToggleCount --
  1841.  *
  1842.  *    This procedure increments or decrements the toggle count for
  1843.  *    a particular tag in a particular node and all its ancestors.
  1844.  *
  1845.  * Results:
  1846.  *    None.
  1847.  *
  1848.  * Side effects:
  1849.  *    The toggle count for tag is adjusted up or down by "delta" in
  1850.  *    nodePtr.
  1851.  *
  1852.  *----------------------------------------------------------------------
  1853.  */
  1854.  
  1855. static void
  1856. ChangeNodeToggleCount(nodePtr, tagPtr, delta)
  1857.     register Node *nodePtr;        /* Node whose toggle count for a tag
  1858.                      * must be changed. */
  1859.     TkTextTag *tagPtr;            /* Information about tag. */
  1860.     int delta;                /* Amount to add to current toggle
  1861.                      * count for tag (may be negative). */
  1862. {
  1863.     register Summary *summaryPtr, *prevPtr;
  1864.  
  1865.     /*
  1866.      * Iterate over the node and all of its ancestors.
  1867.      */
  1868.  
  1869.     for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
  1870.     /*
  1871.      * See if there's already an entry for this tag for this node.  If so,
  1872.      * perhaps all we have to do is adjust its count.
  1873.      */
  1874.     
  1875.     for (prevPtr = NULL, summaryPtr = nodePtr->summaryPtr;
  1876.         summaryPtr != NULL;
  1877.         prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
  1878.         if (summaryPtr->tagPtr != tagPtr) {
  1879.         continue;
  1880.         }
  1881.         summaryPtr->toggleCount += delta;
  1882.         if (summaryPtr->toggleCount > 0) {
  1883.         goto nextAncestor;
  1884.         }
  1885.         if (summaryPtr->toggleCount < 0) {
  1886.         panic("ChangeNodeToggleCount: negative toggle count");
  1887.         }
  1888.     
  1889.         /*
  1890.          * Zero count;  must remove this tag from the list.
  1891.          */
  1892.     
  1893.         if (prevPtr == NULL) {
  1894.         nodePtr->summaryPtr = summaryPtr->nextPtr;
  1895.         } else {
  1896.         prevPtr->nextPtr = summaryPtr->nextPtr;
  1897.         }
  1898.         ckfree((char *) summaryPtr);
  1899.         goto nextAncestor;
  1900.     }
  1901.     
  1902.     /*
  1903.      * This tag isn't in the list.  Add a new entry to the list.
  1904.      */
  1905.     
  1906.     if (delta < 0) {
  1907.         panic("ChangeNodeToggleCount: negative delta, no tag entry");
  1908.     }
  1909.     summaryPtr = (Summary *) ckalloc(sizeof(Summary));
  1910.     summaryPtr->tagPtr = tagPtr;
  1911.     summaryPtr->toggleCount = delta;
  1912.     summaryPtr->nextPtr = nodePtr->summaryPtr;
  1913.     nodePtr->summaryPtr = summaryPtr;
  1914.  
  1915.     nextAncestor:
  1916.     continue;
  1917.     }
  1918. }
  1919.  
  1920. /*
  1921.  *----------------------------------------------------------------------
  1922.  *
  1923.  * TkBTreeCharTagged --
  1924.  *
  1925.  *    Determine whether a particular character has a particular tag.
  1926.  *
  1927.  * Results:
  1928.  *    The return value is 1 if the given tag is in effect at the
  1929.  *    character given by linePtr and ch, and 0 otherwise.
  1930.  *
  1931.  * Side effects:
  1932.  *    None.
  1933.  *
  1934.  *----------------------------------------------------------------------
  1935.  */
  1936.  
  1937. int
  1938. TkBTreeCharTagged(linePtr, ch, tagPtr)
  1939.     TkTextLine *linePtr;        /* Line containing character of
  1940.                      * interest. */
  1941.     int ch;                /* Index of character in linePtr. */
  1942.     TkTextTag *tagPtr;            /* Tag of interest. */
  1943. {
  1944.     register Node *nodePtr;
  1945.     register TkTextLine *siblingLinePtr;
  1946.     int toggles;
  1947.  
  1948.     /*
  1949.      * Count the number of toggles for the tag at the line level (i.e.
  1950.      * in all the sibling lines that precede this one, plus in this line
  1951.      * up to the character of interest.
  1952.      */
  1953.  
  1954.     toggles = 0;
  1955.     for (siblingLinePtr = linePtr->parentPtr->children.linePtr; ;
  1956.         siblingLinePtr = siblingLinePtr->nextPtr) {
  1957.     register TkAnnotation *annotPtr;
  1958.  
  1959.     for (annotPtr = siblingLinePtr->annotPtr;
  1960.         (annotPtr != NULL) && ((siblingLinePtr != linePtr)
  1961.             || (annotPtr->ch <= ch));
  1962.         annotPtr = annotPtr->nextPtr) {
  1963.         if ((annotPtr->type == TK_ANNOT_TOGGLE)
  1964.             && (annotPtr->info.tagPtr == tagPtr)) {
  1965.         toggles++;
  1966.         }
  1967.     }
  1968.     if (siblingLinePtr == linePtr) {
  1969.         break;
  1970.     }
  1971.     }
  1972.  
  1973.     /*
  1974.      * For each node in the ancestry of this line, count the number of
  1975.      * toggles of the given tag in siblings that precede that node.
  1976.      */
  1977.  
  1978.     for (nodePtr = linePtr->parentPtr; nodePtr->parentPtr != NULL;
  1979.         nodePtr = nodePtr->parentPtr) {
  1980.     register Node *siblingPtr;
  1981.     register Summary *summaryPtr;
  1982.  
  1983.     for (siblingPtr = nodePtr->parentPtr->children.nodePtr; 
  1984.         siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
  1985.         for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
  1986.             summaryPtr = summaryPtr->nextPtr) {
  1987.         if (summaryPtr->tagPtr == tagPtr) {
  1988.             toggles += summaryPtr->toggleCount;
  1989.         }
  1990.         }
  1991.     }
  1992.     }
  1993.  
  1994.     /*
  1995.      * An odd number of toggles means that the tag is present at the
  1996.      * given point.
  1997.      */
  1998.  
  1999.     return toggles & 1;
  2000. }
  2001.  
  2002. /*
  2003.  *----------------------------------------------------------------------
  2004.  *
  2005.  * TkBTreeGetTags --
  2006.  *
  2007.  *    Return information about all of the tags that are associated
  2008.  *    with a particular character in a B-tree of text.
  2009.  *
  2010.  * Results:
  2011.  *    The return value is a malloc-ed array containing pointers to
  2012.  *    information for each of the tags that is associated with
  2013.  *    the character at the position given by linePtr and ch.  The
  2014.  *    word at *numTagsPtr is filled in with the number of pointers
  2015.  *    in the array.  It is up to the caller to free the array by
  2016.  *    passing it to free.  If there are no tags at the given character
  2017.  *    then a NULL pointer is returned and *numTagsPtr will be set to 0.
  2018.  *
  2019.  * Side effects:
  2020.  *    None.
  2021.  *
  2022.  *----------------------------------------------------------------------
  2023.  */
  2024.  
  2025.     /* ARGSUSED */
  2026. TkTextTag **
  2027. TkBTreeGetTags(tree, linePtr, ch, numTagsPtr)
  2028.     TkTextBTree tree;        /* Tree to check. */
  2029.     TkTextLine *linePtr;    /* Line containing character of interest. */
  2030.     int ch;            /* Index within linePtr of character for
  2031.                  * which tag information is wanted. */
  2032.     int *numTagsPtr;        /* Store number of tags found at this
  2033.                  * location. */
  2034. {
  2035.     register Node *nodePtr;
  2036.     register TkTextLine *siblingLinePtr;
  2037.     int src, dst;
  2038.     TagInfo tagInfo;
  2039. #define NUM_TAG_INFOS 10
  2040.  
  2041.     tagInfo.numTags = 0;
  2042.     tagInfo.arraySize = NUM_TAG_INFOS;
  2043.     tagInfo.tagPtrs = (TkTextTag **) ckalloc((unsigned)
  2044.         NUM_TAG_INFOS*sizeof(TkTextTag *));
  2045.     tagInfo.counts = (int *) ckalloc((unsigned)
  2046.         NUM_TAG_INFOS*sizeof(int));
  2047.  
  2048.     /*
  2049.      * Record tag toggles at the line level (i.e. in all the sibling
  2050.      * lines that precede this one, plus in this line up to the character
  2051.      * of interest.
  2052.      */
  2053.  
  2054.     for (siblingLinePtr = linePtr->parentPtr->children.linePtr; ;
  2055.         siblingLinePtr = siblingLinePtr->nextPtr) {
  2056.     register TkAnnotation *annotPtr;
  2057.  
  2058.     for (annotPtr = siblingLinePtr->annotPtr;
  2059.         (annotPtr != NULL) && ((siblingLinePtr != linePtr)
  2060.             || (annotPtr->ch <= ch));
  2061.         annotPtr = annotPtr->nextPtr) {
  2062.         if (annotPtr->type == TK_ANNOT_TOGGLE) {
  2063.         IncCount(annotPtr->info.tagPtr, 1, &tagInfo);
  2064.         }
  2065.     }
  2066.     if (siblingLinePtr == linePtr) {
  2067.         break;
  2068.     }
  2069.     }
  2070.  
  2071.     /*
  2072.      * For each node in the ancestry of this line, record tag toggles
  2073.      * for all siblings that precede that node.
  2074.      */
  2075.  
  2076.     for (nodePtr = linePtr->parentPtr; nodePtr->parentPtr != NULL;
  2077.         nodePtr = nodePtr->parentPtr) {
  2078.     register Node *siblingPtr;
  2079.     register Summary *summaryPtr;
  2080.  
  2081.     for (siblingPtr = nodePtr->parentPtr->children.nodePtr; 
  2082.         siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
  2083.         for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
  2084.             summaryPtr = summaryPtr->nextPtr) {
  2085.         IncCount(summaryPtr->tagPtr, summaryPtr->toggleCount, &tagInfo);
  2086.         }
  2087.     }
  2088.     }
  2089.  
  2090.     /*
  2091.      * Go through the tag information and squash out all of the tags
  2092.      * that have even toggle counts (these tags exist before the point
  2093.      * of interest, but not at the desired character itself).
  2094.      */
  2095.  
  2096.     for (src = 0, dst = 0; src < tagInfo.numTags; src++) {
  2097.     if (tagInfo.counts[src] & 1) {
  2098.         tagInfo.tagPtrs[dst] = tagInfo.tagPtrs[src];
  2099.         dst++;
  2100.     }
  2101.     }
  2102.     *numTagsPtr = dst;
  2103.     ckfree((char *) tagInfo.counts);
  2104.     if (dst == 0) {
  2105.     ckfree((char *) tagInfo.tagPtrs);
  2106.     return NULL;
  2107.     }
  2108.     return tagInfo.tagPtrs;
  2109. }
  2110.  
  2111. /*
  2112.  *----------------------------------------------------------------------
  2113.  *
  2114.  * IncCount --
  2115.  *
  2116.  *    This is a utility procedure used by TkBTreeGetTags.  It
  2117.  *    increments the count for a particular tag, adding a new
  2118.  *    entry for that tag if there wasn't one previously.
  2119.  *
  2120.  * Results:
  2121.  *    None.
  2122.  *
  2123.  * Side effects:
  2124.  *    The information at *tagInfoPtr may be modified, and the arrays
  2125.  *    may be reallocated to make them larger.
  2126.  *
  2127.  *----------------------------------------------------------------------
  2128.  */
  2129.  
  2130. static void
  2131. IncCount(tagPtr, inc, tagInfoPtr)
  2132.     TkTextTag *tagPtr;        /* Handle for tag. */
  2133.     int inc;            /* Amount by which to increment tag count. */
  2134.     TagInfo *tagInfoPtr;    /* Holds cumulative information about tags;
  2135.                  * increment count here. */
  2136. {
  2137.     register TkTextTag **tagPtrPtr;
  2138.     int count;
  2139.  
  2140.     for (tagPtrPtr = tagInfoPtr->tagPtrs, count = tagInfoPtr->numTags;
  2141.         count > 0; tagPtrPtr++, count--) {
  2142.     if (*tagPtrPtr == tagPtr) {
  2143.         tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
  2144.         return;
  2145.     }
  2146.     }
  2147.  
  2148.     /*
  2149.      * There isn't currently an entry for this tag, so we have to
  2150.      * make a new one.  If the arrays are full, then enlarge the
  2151.      * arrays first.
  2152.      */
  2153.  
  2154.     if (tagInfoPtr->numTags == tagInfoPtr->arraySize) {
  2155.     TkTextTag **newTags;
  2156.     int *newCounts, newSize;
  2157.  
  2158.     newSize = 2*tagInfoPtr->arraySize;
  2159.     newTags = (TkTextTag **) ckalloc((unsigned)
  2160.         (newSize*sizeof(TkTextTag *)));
  2161.     memcpy((VOID *) newTags, (VOID *) tagInfoPtr->tagPtrs,
  2162.         tagInfoPtr->arraySize * sizeof(TkTextTag *));
  2163.     ckfree((char *) tagInfoPtr->tagPtrs);
  2164.     tagInfoPtr->tagPtrs = newTags;
  2165.     newCounts = (int *) ckalloc((unsigned) (newSize*sizeof(int)));
  2166.     memcpy((VOID *) newCounts, (VOID *) tagInfoPtr->counts,
  2167.         tagInfoPtr->arraySize * sizeof(int));
  2168.     ckfree((char *) tagInfoPtr->counts);
  2169.     tagInfoPtr->counts = newCounts;
  2170.     tagInfoPtr->arraySize = newSize;
  2171.     }
  2172.  
  2173.     tagInfoPtr->tagPtrs[tagInfoPtr->numTags] = tagPtr;
  2174.     tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
  2175.     tagInfoPtr->numTags++;
  2176. }
  2177.  
  2178. /*
  2179.  *----------------------------------------------------------------------
  2180.  *
  2181.  * CheckNodeConsistency --
  2182.  *
  2183.  *    This procedure is called as part of consistency checking for
  2184.  *    B-trees:  it checks several aspects of a node and also runs
  2185.  *    checks recursively on the node's children.
  2186.  *
  2187.  * Results:
  2188.  *    None.
  2189.  *
  2190.  * Side effects:
  2191.  *    If anything suspicious is found in the tree structure, the
  2192.  *    procedure panics.
  2193.  *
  2194.  *----------------------------------------------------------------------
  2195.  */
  2196.  
  2197. static void
  2198. CheckNodeConsistency(nodePtr)
  2199.     register Node *nodePtr;        /* Node whose subtree should be
  2200.                      * checked. */
  2201. {
  2202.     register Node *childNodePtr;
  2203.     register Summary *summaryPtr, *summaryPtr2;
  2204.     register TkAnnotation *annotPtr;
  2205.     register TkTextLine *linePtr;
  2206.     register char *p;
  2207.     int numChildren, numLines, toggleCount, minChildren, index, numBytes;
  2208.  
  2209.     if (nodePtr->parentPtr != NULL) {
  2210.     minChildren = MIN_CHILDREN;
  2211.     } else if (nodePtr->level > 0) {
  2212.     minChildren = 2;
  2213.     } else  {
  2214.     minChildren = 1;
  2215.     }
  2216.     if ((nodePtr->numChildren < minChildren)
  2217.         || (nodePtr->numChildren > MAX_CHILDREN)) {
  2218.     panic("CheckNodeConsistency found bad child count (%d)",
  2219.         nodePtr->numChildren);
  2220.     }
  2221.  
  2222.     numChildren = 0;
  2223.     numLines = 0;
  2224.     if (nodePtr->level == 0) {
  2225.     for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
  2226.         linePtr = linePtr->nextPtr) {
  2227.         if (linePtr->parentPtr != nodePtr) {
  2228.         panic("CheckNodeConsistency found line that %s",
  2229.             "didn't point to parent");
  2230.         }
  2231.         for (p = linePtr->bytes, numBytes = 0; *p != 0; p++, numBytes++) {
  2232.         if ((*p == '\n') && (numBytes != linePtr->numBytes-1)) {
  2233.             panic("CheckNodeConsistency found line with extra newline");
  2234.         }
  2235.         }
  2236.         if (numBytes != linePtr->numBytes) {
  2237.         panic("CheckNodeConsistency found line with bad numBytes");
  2238.         }
  2239.         if (linePtr->bytes[numBytes-1] != '\n') {
  2240.         panic("CheckNodeConsistency found line with no newline");
  2241.         }
  2242.         index = 0;
  2243.         for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
  2244.             annotPtr = annotPtr->nextPtr) {
  2245.         if (annotPtr->ch < index) {
  2246.             panic("CheckNodeConsistency found %s (%d %d)",
  2247.                 "out-of-order tag indices", index,
  2248.                 annotPtr->ch);
  2249.         }
  2250.         index = annotPtr->ch;
  2251.         if (annotPtr->type == TK_ANNOT_TOGGLE) {
  2252.             for (summaryPtr = nodePtr->summaryPtr; ;
  2253.                 summaryPtr = summaryPtr->nextPtr) {
  2254.             if (summaryPtr == NULL) {
  2255.                 panic("CheckNodeConsistency found line %s",
  2256.                     "tag with no node tag: %s",
  2257.                     summaryPtr->tagPtr->name);
  2258.             }
  2259.             if (summaryPtr->tagPtr == annotPtr->info.tagPtr) {
  2260.                 break;
  2261.             }
  2262.             }
  2263.         }
  2264.         }
  2265.         numChildren++;
  2266.         numLines++;
  2267.     }
  2268.     } else {
  2269.     for (childNodePtr = nodePtr->children.nodePtr; childNodePtr != NULL;
  2270.         childNodePtr = childNodePtr->nextPtr) {
  2271.         CheckNodeConsistency(childNodePtr);
  2272.         for (summaryPtr = childNodePtr->summaryPtr; summaryPtr != NULL;
  2273.             summaryPtr = summaryPtr->nextPtr) {
  2274.         for (summaryPtr2 = nodePtr->summaryPtr; ;
  2275.             summaryPtr2 = summaryPtr2->nextPtr) {
  2276.             if (summaryPtr2 == NULL) {
  2277.             panic("CheckNodeConsistency found %s (%s)",
  2278.                 "node tag with no parent tag",
  2279.                 summaryPtr->tagPtr->name);
  2280.             }
  2281.             if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
  2282.             break;
  2283.             }
  2284.         }
  2285.         }
  2286.         numChildren++;
  2287.         numLines += childNodePtr->numLines;
  2288.         if (childNodePtr->parentPtr != nodePtr) {
  2289.         panic("CheckNodeConsistency found node that %s",
  2290.             "didn't point to parent");
  2291.         }
  2292.         if (childNodePtr->level != (nodePtr->level-1)) {
  2293.         panic("CheckNodeConsistency found level mismatch (%d %d)",
  2294.             nodePtr->level, childNodePtr->level);
  2295.         }
  2296.     }
  2297.     }
  2298.     if (numChildren != nodePtr->numChildren) {
  2299.     panic("CheckNodeConsistency found mismatch in numChildren (%d %d)",
  2300.         numChildren, nodePtr->numChildren);
  2301.     }
  2302.     if (numLines != nodePtr->numLines) {
  2303.     panic("CheckNodeConsistency found mismatch in numLines (%d %d)",
  2304.         numLines, nodePtr->numLines);
  2305.     }
  2306.  
  2307.     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
  2308.         summaryPtr = summaryPtr->nextPtr) {
  2309.     toggleCount = 0;
  2310.     if (nodePtr->level == 0) {
  2311.         for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
  2312.             linePtr = linePtr->nextPtr) {
  2313.         for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
  2314.             annotPtr = annotPtr->nextPtr) {
  2315.             if (annotPtr->info.tagPtr == summaryPtr->tagPtr) {
  2316.             toggleCount++;
  2317.             }
  2318.         }
  2319.         }
  2320.     } else {
  2321.         for (childNodePtr = nodePtr->children.nodePtr;
  2322.             childNodePtr != NULL;
  2323.             childNodePtr = childNodePtr->nextPtr) {
  2324.         for (summaryPtr2 = childNodePtr->summaryPtr;
  2325.             summaryPtr2 != NULL;
  2326.             summaryPtr2 = summaryPtr2->nextPtr) {
  2327.             if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
  2328.             toggleCount += summaryPtr2->toggleCount;
  2329.             }
  2330.         }
  2331.         }
  2332.     }
  2333.     if (toggleCount != summaryPtr->toggleCount) {
  2334.         panic("CheckNodeConsistency found mismatch in toggleCount (%d %d)",
  2335.             toggleCount, summaryPtr->toggleCount);
  2336.     }
  2337.     for (summaryPtr2 = summaryPtr->nextPtr; summaryPtr2 != NULL;
  2338.         summaryPtr2 = summaryPtr2->nextPtr) {
  2339.         if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
  2340.         panic("CheckNodeConsistency found duplicated node tag: %s",
  2341.             summaryPtr->tagPtr->name);
  2342.         }
  2343.     }
  2344.     }
  2345. }
  2346.  
  2347. /*
  2348.  *----------------------------------------------------------------------
  2349.  *
  2350.  * TkBTreeNumLines --
  2351.  *
  2352.  *    This procedure returns a count of the number of lines of
  2353.  *    text present in a given B-tree.
  2354.  *
  2355.  * Results:
  2356.  *    The return value is a count of the number of lines in tree.
  2357.  *
  2358.  * Side effects:
  2359.  *    None.
  2360.  *
  2361.  *----------------------------------------------------------------------
  2362.  */
  2363.  
  2364. int
  2365. TkBTreeNumLines(tree)
  2366.     TkTextBTree tree;            /* Information about tree. */
  2367. {
  2368.     BTree *treePtr = (BTree *) tree;
  2369.     return treePtr->rootPtr->numLines;
  2370. }
  2371.